|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 計 ： [けい] 1. (n,n-suf) plan ・ 計算 ： [けいさん] 1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast ・ 複 ： [ふく] 1. (n,pref) double 2. compound ・ 複雑 ： [ふくざつ] 1. (adj-na,n) complexity 2. complication ・ 雑 ： [ざつ] 1. (adj-na,n) rough 2. crude ・ 理 ： [り] 【名詞】 1. reason ・ 理論 ： [りろん] 【名詞】 1. theory ・ 論 ： [ろん] 【名詞】 1. (1) argument 2. discussion 3. dispute 4. controversy 5. discourse 6. debate 7. (2) theory 8. doctrine 9. (3) essay 10. treatise 1 1. comment
計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である（チューリングマシンの停止問題が決定不能であるため）。すなわち、PR は構文的クラスであり、R は意味論的クラスである。 一方、任意の帰納的可算集合（REも参照）を原始再帰関数を次のように使って枚挙可能である。入力 (''M'', ''k'') を与えたとき（''M'' はチューリングマシン、''k'' は整数）、''M'' が ''k'' ステップ以内に停止するなら ''M'' を出力するものとする。そうでない場合は何も出力しない。すると (''M'', ''k'') の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する ''M'' の集合に他ならない。 == 関連項目 == * 原始再帰関数 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PR (計算複雑性理論)」の詳細全文を読む スポンサード リンク
|